const array1 = [1, 5, 1,  3, 4, 7, 3,  5]
const array2 = [2, 3, 4, 5, 5, 6, 2, 1, [3, 4, 4, [9, 9, 10]], [5, 5, 7]]
const array3 = [2, 3, 1, 7, 4, 9, 6, 5]
// 数组去重
class MyArray {
  constructor() {

  }

  repeat1 (array) {
    // 浅层
    return [...new Set(array)]
  }

  repeat2 (array) {
    // 深层去重
    let result = []
    array.map(item => {
      if (Array.isArray(item)) {
        result = result.concat(this.repeat2(item)) 
      } else {
        result.push(item)
      }
    })
    // return [...new Set(result)].sort((a, b) => a - b) // 排个序
    return this.mySort1([...new Set(result)]) // 排个序
  }

  // 选择排序 通过每一次的比较选出最小或者最大的放在首位、第二位...以此类推
  mySort1 (array) {
    for (let i in array) {
      for (let j in array) {
        if (array[i] >= array[j]) {
          let save = array[j]
          array[j] = array[i]
          array[i] = save
        }
      }
    }
    return array
  }

  // 冒泡排序 每轮比较相邻的两个数的大小，大的或者小的进行交换
  mySort2 (array) {
    for (let i = 0; i < array.length; i++) {
      for (let j = 0; j < array.length; j++) {
        if (array[j] > array[j+1]) {
          let temp = array[j]
          array[j] = array[j+1]
          array[j+1] = temp
        }
      }
    }
    return array
  }

  // 插入排序
  mySort3 (array) {

  }

  // 希尔排序
  mySort4 (array) {

  }

  // 快速排序 - 将数组取出中间值，以它为基准，按照大小分为两个数组，而后合并并递归这两个数组，直到数组长度小于等于1
  mySort5 (array) {
    if (array.length <= 1) {
      return array
    }
    // 取中间的基准值，同时将这个值从源数组中移除
    const [middle] = array.splice(Math.floor(array.length / 2), 1)
    let left = []
    let right = []
    for (let i in array) {
      if (array[i] > middle) {
        right.push(array[i])
      } else {
        left.push(array[i])
      }
    }
    return this.mySort5(left).concat(middle, this.mySort5(right))
  }

  // 归并排序
  mySort6 (array) {

  }

  // 堆排序
  mySort7 (array) {

  }

  // 桶排序
  mySort8 (array) {

  }

  // 基数排序
  mySort9 (array) {

  }

  /*
    给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
    说明：
      你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
      举个例子 [2,2,1,1,5,5,100],找出100
  */
  seekElement (array) {
    let ans = 0
    for(let val of array) {
      ans ^= val
    }
    return ans
  }
}

const r = new MyArray
console.log('repeat1 -->', r.mySort5(array3));
